package leetcode.slidingwindow;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//3. 无重复字符的最长子串  -----滑动窗口
public class LengthOfLongestSubstring {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring2("abcabcbb"));
    }
    //暴力---会超时
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n <= 1) {
            return n;
        }
        int maxLength=1;
        for (int i =0;i<s.length();i++){
            for (int j = i+1;j<s.length();j++){
                if (allUnique(s, i, j)){
                    maxLength = Math.max(maxLength,j-i+1);
                }
            }
        }
        return maxLength;
    }
    private static boolean allUnique(String s,int start,int end){
        Set<Character> set = new HashSet<>();
        for (int i=start;i<=end;i++){
            if (set.contains(s.charAt(i))){
                return false;
            }
            set.add(s.charAt(i));
        }
        return true;
    }


    //滑动窗口  -----左指针需要一步一步的移动到重复的元素
    public static int lengthOfLongestSubstring2(String s) {
        if (s.length()<=1){
            return s.length();
        }
        int left=0;
        int right=0;
        int maxLength=1;
        Set<Character> window = new HashSet<>();
        while (right<s.length()){
            while (window.contains(s.charAt(right))){
                window.remove(s.charAt(left));
                left++;  //移动左边界，直到把重复元素移除
            }
            maxLength = Math.max(maxLength,right-left+1);
            window.add(s.charAt(right));
            right++;
        }
        return maxLength;
    }


    //滑动窗口优化----左指针直接移动到重复元素的下一个位置
    public static int lengthOfLongestSubstring3(String s) {
        Map<Character,Integer> window = new HashMap<>();
        if (s.length()<=1){
            return s.length();
        }
        int left=0;
        int right=0;
        int maxLength=1;
        while (right<s.length()){
            //判断right指针指向的元素是否出现过,如果没有返回-1，如果有返回value
            int rightCharIndex = window.getOrDefault(s.charAt(right),-1);
            left = Math.max(left,rightCharIndex+1); //如果没有出现过，rightCharIndex+1=0，因为left肯定大于等于0
                                                    //所以如果出现过就肯定取值rightCharIndex+1 ，没出现过就取值left,
                                                    // 取最大值，保证left只向前移，不后退

            maxLength = Math.max(maxLength,right-left+1);
            window.put(s.charAt(right),right);
            right++;
        }

        return maxLength;
    }



}
